package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC117 {
    public long startExecuteTime = System.currentTimeMillis();


    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 有点意思的解法
     * @return:
     */
    class Solution {
        // 方法2 递归
        public Node connect(Node root) {
            if (root == null) return root;
            nextConnect(root);
            return root;
        }

        public void nextConnect(Node root) {
            if (root == null) return;
            Node pre = null; // 用来记录两指向节点的左节点
            Node tempRoot = null;  // 用来记录第一个节点，作为递归的输入

            while (root != null) {// 循环根据next指针遍历当前层
                if (root.left != null) { // 左子
                    if (pre != null) {
                        pre.next = root.left;

                    }
                    pre = root.left;
                    if (tempRoot == null) {
                        tempRoot = root.left;
                    }
                }
                if (root.right != null) {// 右子
                    if (pre != null) {
                        pre.next = root.right;

                    }
                    pre = root.right;
                    if (tempRoot == null) {
                        tempRoot = root.right;
                    }
                }
                root = root.next;
            }

            nextConnect(tempRoot);
        }
    }

    public void run() {
        Solution solution = new Solution();
        Node n_1 = new Node(1);
        Node n_2 = new Node(2);
        Node n_3 = new Node(3);
        Node n_4 = new Node(4);
        Node n_5 = new Node(5);
        Node n_7 = new Node(7);

        n_1.left = n_2;
        n_1.right = n_3;
        n_2.left = n_4;
        n_2.right = n_5;
        n_3.right = n_7;

        solution.connect(n_1);
    }

    public static void main(String[] args) throws Exception {
        LC117 an = new LC117();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
